//给你一个正方形字符数组 board ，你从数组最右下方的字符 'S' 出发。 
//
// 你的目标是到达数组最左上角的字符 'E' ，数组剩余的部分为数字字符 1, 2, ..., 9 或者障碍 'X'。在每一步移动中，你可以向上、向左或者左上
//方移动，可以移动的前提是到达的格子没有障碍。 
//
// 一条路径的 「得分」 定义为：路径上所有数字的和。 
//
// 请你返回一个列表，包含两个整数：第一个整数是 「得分」 的最大值，第二个整数是得到最大得分的方案数，请把结果对 10^9 + 7 取余。 
//
// 如果没有任何路径可以到达终点，请返回 [0, 0] 。 
//
// 
//
// 示例 1： 
//
// 
//输入：board = ["E23","2X2","12S"]
//输出：[7,1]
// 
//
// 示例 2： 
//
// 
//输入：board = ["E12","1X1","21S"]
//输出：[4,2]
// 
//
// 示例 3： 
//
// 
//输入：board = ["E11","XXX","11S"]
//输出：[0,0]
// 
//
// 
//
// 提示： 
//
// 
// 2 <= board.length == board[i].length <= 100 
// 
// Related Topics数组 | 动态规划 | 矩阵 
//
// 👍 63, 👎 0 
//
//
//
//

package leetcode.editor.cn;

import java.util.Arrays;
import java.util.List;

class NumberOfPathsWithMaxScore {
    public static void main(String[] args) {
        Solution solution = new NumberOfPathsWithMaxScore().new Solution();
        solution.pathsWithMaxScore(Arrays.asList("E23", "2X2", "12S"));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        // DFS（TTL），需要记忆化DFS + 剪枝
        /*int cnt = 0, maxScore = 0, mod = (int) 1e9 + 7, m, n;
        int[][] dir = {{-1, 0}, {0, -1}, {-1, -1}};

        public int[] pathsWithMaxScore(List<String> board) {
            m = board.size();
            n = board.get(0).length();
            char[][] arr = new char[m][n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    arr[i][j] = board.get(i).charAt(j);
                }
            }

            dfs(arr, m - 1, n - 1, 0);

            return new int[]{maxScore, cnt};
        }


        public void dfs(char[][] arr, int i, int j, int score) {
            if (i < 0 || j < 0 || i >= m || j >= n) return;
            if (arr[i][j] == 'X') return;

            if (arr[i][j] == 'E') {
                if (maxScore == score) {
                    cnt++;
                    cnt %= mod;
                } else if (maxScore < score) {
                    maxScore = score;
                    cnt = 1;
                }
                return;
            }

            if (arr[i][j] != 'S') score += Integer.parseInt(String.valueOf(arr[i][j]));

            for (int[] d : dir) {
                int x = i + d[0], y = j + d[1];
                dfs(arr, x, y, score);
            }
        }*/

        // 路径dp
        // https://leetcode.cn/leetbook/read/path-problems-in-dynamic-programming/r87czj/
        int INF = Integer.MIN_VALUE;
        int mod = (int) 1e9 + 7;
        int n;

        public int[] pathsWithMaxScore(List<String> board) {
            n = board.size();
            char[][] arr = new char[n][n];
            for (int i = 0; i < n; i++) {
                arr[i] = board.get(i).toCharArray();
            }

            // 从右下角到达该位置i的最大得分
            int[] f = new int[n * n];
            // 从右下角到达该位置i的等于最大得分的路径
            int[] g = new int[n * n];

            for (int i = n - 1; i >= 0; i--) {
                for (int j = n - 1; j >= 0; j--) {
                    int idx = getIndex(i, j);

                    // 如果在右下角，初始化路径值
                    if (i == n - 1 && j == n - 1) {
                        g[idx] = 1;
                        continue;
                    }

                    // 如果遇到障碍，那么得分未INF
                    if (arr[i][j] == 'X') {
                        f[idx] = INF;
                        continue;
                    }

                    int val = (i == 0 && j == 0) ? 0 : arr[i][j] - '0';

                    // 进行三个方向的递推
                    int u = INF, t = 0;
                    if (i + 1 < n) {
                        // 得到上次的得分和次数
                        int cur = f[getIndex(i + 1, j)] + val;
                        int cnt = g[getIndex(i + 1, j)];
                        int[] res = update(cur, cnt, u, t);
                        u = res[0];
                        t = res[1];
                    }

                    if (j + 1 < n) {
                        // 得到上次的得分和次数
                        int cur = f[getIndex(i, j + 1)] + val;
                        int cnt = g[getIndex(i, j + 1)];
                        int[] res = update(cur, cnt, u, t);
                        u = res[0];
                        t = res[1];
                    }

                    if (i + 1 < n && j + 1 < n) {
                        // 得到上次的得分和次数
                        int cur = f[getIndex(i + 1, j + 1)] + val;
                        int cnt = g[getIndex(i + 1, j + 1)];
                        int[] res = update(cur, cnt, u, t);
                        u = res[0];
                        t = res[1];
                    }

                    // 更新dp值
                    f[idx] = u < 0 ? INF : u;
                    g[idx] = t;
                }
            }

            int[] ans = new int[2];
            // 判断是否能到达
            // 如果终点不可达（动规值为 INF）时，写入 0
            ans[0] = f[getIndex(0, 0)] == INF ? 0 : f[getIndex(0, 0)];
            // 如果终点不可达（动规值为 INF）时，写入 0
            ans[1] = f[getIndex(0, 0)] == INF ? 0 : g[getIndex(0, 0)];
            return ans;
        }

        /**
         * 更新dp
         *
         * @param cur 当前得分
         * @param cnt 等于当前得分的次数
         * @param u   最大的分
         * @param t   等于最大得分的次数
         * @return
         */
        public int[] update(int cur, int cnt, int u, int t) {
            int[] ans = new int[]{u, t};

            if (cur > u) {
                // 大于则进行更新
                ans[0] = cur;
                ans[1] = cnt;
            } else if (cur == u && cur != INF){
                // 等于则加上次数
                ans[1] += cnt;
            }

            ans[1] %= mod;

            return ans;
        }

        public int getIndex(int i, int j) {
            return i * n + j;
        }

        public int[] parseIdx(int idx) {
            return new int[]{idx / n, idx % n};
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
